import java.io.*;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;
import java.util.Set;

public class VRPOD {
    public static void main(String[] args) throws FileNotFoundException {
        // 读取数据
        int num_c;
        int num_od;
        int[][] customer; // 客户点：x, y, demand
        int[][] od; // OD：id,x,y
        String file1 = "src/data/OD_destination_25.txt";
        String file2 = "src/data/solomon 25.txt";
        // 读取客户点数据
        Scanner sc = new Scanner(new BufferedReader(new FileReader(file2)));
        num_c = sc.nextInt();
        customer = new int[num_c][3];
        sc.nextLine();
        sc.nextLine();
        for (int i = 0; i < num_c; i++) {
            customer[i][0] = sc.nextInt();
            customer[i][1] = sc.nextInt();
            customer[i][2] = sc.nextInt();
        }
        sc.close();
        // 读取OD数据
        sc = new Scanner(new BufferedReader(new FileReader(file1)));
        num_od = sc.nextInt();
        od = new int[num_od][3];
        sc.nextLine();
        sc.nextLine();
        for (int i = 0; i < num_od; i++) {
            od[i][0] = sc.nextInt();
            od[i][1] = sc.nextInt();
            od[i][2] = sc.nextInt();
        }
        sc.close();
        // 生成算例
        Instance instance = new Instance(num_c, num_od, 200, 1.2, 1.4, customer, od);
        // 输出所有的点
//        for (int i = 0; i < instance.getNodes().length; i++) {
//            System.out.println(instance.getNodes()[i][0]+", "+instance.getNodes()[i][1]);
//        }

        // 计算初始解（假设所有的客户都是由RD服务）
        heuristic(instance);
    }

    // 求解算法（类似于贪心算法的算法，应该只能适用于生成初始解）
    public static void heuristic(Instance instance) {
        int num_node = instance.getNum_c() + instance.getNum_od();
        // 作为初始解x，每个客户点与OD目的地点都被RD访问，且都构成一个单独路径
        HashMap<Integer, ArrayList<Integer>> x = new HashMap<>();
        for (int i = 1; i < num_node; i++) {
            ArrayList<Integer> r = new ArrayList<>();
            r.add(0);
            r.add(i);
            r.add(0);
            x.put(i, r);
        }

        // 合并路径，以此来减少数量，进行初次优化
        double maxsaving = 1;
        ArrayList<Integer> tour = new ArrayList<>();
        while (maxsaving > 0) {
            ArrayList<Integer> savetour = new ArrayList<>();
            maxsaving = 0;

            int parent1 = instance.getNum_c() + instance.getNum_od() + 1;
            int parent2 = instance.getNum_c() + instance.getNum_od() + 1;

            // i和j都是作为x之中的key值
            for (int i = 1; i < num_node; i++) {
                for (int j = i + 1; j < num_node; j++) {

                    // 通过索引 i j 从路径集合中取出路径
                    // i，j必须存在于x的key集合中
                    // i，j索引取出的路径，都不能是OD路径
                    // i，j索引，必须有一个是客户点路径
                    if ((x.containsKey(i) && x.containsKey(j))
                            && (!check_OD(x.get(i), instance) && !check_OD(x.get(j), instance))
                            && (i < instance.getNum_c() || j < instance.getNum_c())) {

                        tour = newtour(x.get(i), x.get(j));

                        // 把两个取出的路径合并，要小于之前两个路径的成本和；
                        // 新路径的载量不能超过Q
                        // 生成的新路径不能由OD目的地点
                        if ((distance(x.get(i), instance) + distance(x.get(j), instance) - distance(tour, instance)) > maxsaving
                                && tour.get(tour.size() - 2) < instance.getNum_c()
                                && capacity(tour, instance) <= instance.getQ()
                                && (i < instance.getNum_c() && j < instance.getNum_c())) {
                            savetour = newtour(x.get(i), x.get(j));
                            maxsaving = distance(x.get(i), instance) + distance(x.get(j), instance) - distance(newtour(x.get(i), x.get(j)), instance);
                            parent1 = i;
                            parent2 = j;
                        }

                        // 把两个取出的路径合并，要小于之前两个路径的成本和；
                        // OD配送，其访问点个数为4：仓库->客户点->目的地->仓库
                        // 配送距离在OD的可接受范围内
                        else if (tour.size() == 4
                                && (distance(x.get(i), instance) + distance(x.get(j), instance) - distance(tour, instance)) > maxsaving
                                && x.get(j).get(x.get(j).size() - 2) > instance.getNum_c()
                                && distance(tour, instance) < instance.getDis()[0][j] * instance.getMax_dev()) {
                            savetour = newtour(x.get(i), x.get(j));
                            maxsaving = distance(x.get(i), instance) + distance(x.get(j), instance) - distance(newtour(x.get(i), x.get(j)), instance);
                            parent1 = i;
                            parent2 = j;
                        }
                    }
                }
            }

            // 如果上一步进行了改进
            if (parent1 != instance.getNum_c() + instance.getNum_od() + 1) {
                x.remove(parent1);
                x.remove(parent2);
                x.put(parent1, savetour);
            }
        }

        // 对每条由RD配送的路径，进行访问顺序的重新优化
        Set<Integer> sets = x.keySet();
        for (Integer i : sets) {
            if (check_OD(x.get(i), instance)) {
                Tabu.init(x.get(i), instance.getDis());
                Tabu.solve();
            }
        }

        // 输出所有路径
        for (Integer i : sets) {
            System.out.print("输出路径：");
            if (x.get(i).size() == 0) continue;
            for (int j = 0; j < x.get(i).size(); j++) {
                System.out.print(x.get(i).get(j) + "->");
            }
            System.out.println();
        }
    }

    // 计算路径的总距离
    public static double distance(ArrayList<Integer> r, Instance instance) {
        double dis = 0;
        // 判断是不是OD路径（如果倒数第二个访问点的序号大于等于26，那么就是OD目的地，为OD路径）
        if (r.get(r.size() - 2) >= instance.getNum_c()) {
            for (int i = 0; i < r.size() - 2; i++) {
                dis += instance.getDis()[r.get(i)][r.get(i + 1)];
            }

        } else {
            for (int i = 0; i < r.size() - 1; i++) {
                dis += instance.getDis()[r.get(i)][r.get(i + 1)];
            }
        }
        return dis;
    }

    // 合并路径
    public static ArrayList<Integer> newtour(ArrayList<Integer> r1, ArrayList<Integer> r2) {
        ArrayList<Integer> newR = new ArrayList<>();
        newR.add(0);
        // 先暂且让两条路径直接合并
        for (int i = 1; i < r1.size() - 1; i++) {
            newR.add(r1.get(i));
        }
        for (int i = 1; i < r2.size() - 1; i++) {
            newR.add(r2.get(i));
        }
        newR.add(0);
        return newR;
    }

    // 计算路径载量
    public static int capacity(ArrayList<Integer> r, Instance instance) {
        int capacity = 0;
        for (int i = 1; i < r.size() - 1; i++) {
            capacity += instance.getNodesRD()[r.get(i)][2];
        }
        return capacity;
    }

    // 对路径进行重新访问顺序的优化（这就是一个TSP问题了）
    // 处理此TSP问题，可以使用精确算法或者启发式算法，这里我像上面一样，使用一个贪心算法计算
    // 专门写了个禁忌搜索算法，解TSP，以此来优化RD路径

    // 判断路径是否为OD路径
    public static boolean check_OD(ArrayList<Integer> r, Instance instance) {
        if (r == null) return false;
        if (r.size() == 4 && r.get(r.size() - 2) >= instance.getNum_c()) {
            return true;
        }
        return false;
    }
}